#ifndef TREE_BUILDER_H
#define TREE_BUILDER_H

#include <string>
#include <unordered_set>
#include <unordered_map>
#include <stack>
#include <vector>
using namespace std;

struct TreeNode{
	TreeNode(int index){node_idx = index;};
	

	int node_idx; // index of the nodes

	unordered_map<int,int> graph_nodes; // first element is the graph node index, second element is the index for the distance matrix

	vector<vector<double> > dist_mat; // distance matrix

	vector<int> children;	// index of the children tree nodes
	vector<int> parent;		// index of the parents tree nodes		
};


class TreeBuilder{
public:
	TreeBuilder(int non_root_node_size, string in_dir, string out_dir);

	~TreeBuilder();

public:
	int reduction_factor;
	vector<unordered_set<int> > graph_adj_list; // adjacency of the original graph

	// read adjacency list from file
	void ExtractGraphStruct(string in_dir);

	TreeNode* tree_root;
	vector<TreeNode*> built_nodes;

	// construct the tree
	void DecomposeGraph(vector<unordered_set<int> >& adj_list);
};

#endif